#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣310. 最小高度树
// 【难度】中等
// 【提交】2025.10.14 https://leetcode.cn/problems/minimum-height-trees/submissions/670585271/
// 【标签】图；拓扑排序；广度优先搜索
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return {0};
        vector<int> d(n, 0);
        vector<vector<int>> g(n);
        for(auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
            d[e[0]]++;
            d[e[1]]++;
        }
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(d[i] == 1) q.push(i);
        }
        while(n > 2) {
            int k = q.size();
            n -= k;
            for(int i = 0; i < k; i++) {
                int t = q.front();
                q.pop();
                for(auto& v : g[t]) {
                    d[v]--;
                    if(d[v] == 1) q.push(v);
                }
            }
        }
        vector<int> res;
        while(!q.empty()) {
            res.push_back(q.front());
            q.pop();
        }
        return res;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个包含n个节点的树（无向无环图），找到所有的根节点，使得以这些节点为根时树的高度最小。
 * 模型：拓扑排序+广度优先搜索，通过逐层删除叶子节点找到中心节点。
 * 
 * 二、标准解法状态设计
 * 1. 构建图的邻接表和度数数组。
 * 2. 将所有叶子节点（度数为1）加入队列。
 * 3. 逐层删除叶子节点，直到剩余节点数不超过2。
 * 4. 剩余的节点即为最小高度树的根节点。
 * 
 * 三、你的实现思路
 * 使用拓扑排序的思想，从外向内逐层删除叶子节点。
 * 最终剩下的1个或2个节点就是最小高度树的根节点。
 * 
 * 四、逐行注释（带细节提醒）
 * if(n == 1) return {0}; // 特殊情况处理
 * 
 * vector<int> d(n, 0); // 度数数组
 * vector<vector<int>> g(n); // 邻接表
 * 
 * for(auto& e : edges) { // 构建图
 *     g[e[0]].push_back(e[1]);
 *     g[e[1]].push_back(e[0]);
 *     d[e[0]]++; // 更新度数
 *     d[e[1]]++;
 * }
 * 
 * queue<int> q; // 初始化队列
 * for(int i = 0; i < n; i++) { // 将所有叶子节点入队
 *     if(d[i] == 1) q.push(i);
 * }
 * 
 * while(n > 2) { // 拓扑排序过程
 *     int k = q.size(); // 当前层叶子节点数
 *     n -= k; // 更新剩余节点数
 *     
 *     for(int i = 0; i < k; i++) { // 处理当前层
 *         int t = q.front(); q.pop();
 *         for(auto& v : g[t]) { // 更新邻居
 *             d[v]--;
 *             if(d[v] == 1) q.push(v); // 新叶子节点入队
 *         }
 *     }
 * }
 * 
 * vector<int> res; // 收集结果
 * while(!q.empty()) {
 *     res.push_back(q.front()); q.pop();
 * }
 * return res;
 * 
 * 五、正确性证明
 * 最小高度树的根节点一定是图中最"中心"的节点。
 * 通过逐层删除叶子节点，我们不断向中心收缩，最终剩下的节点就是最中心的节点。
 * 对于树状结构，最终会剩下1个或2个中心节点。
 * 
 * 六、复杂度
 * 时间：O(n)，每个节点和边只被处理一次。
 * 空间：O(n)，需要存储邻接表和度数数组。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法高效，只需线性时间；
 *   - 思路巧妙，利用了拓扑排序的思想；
 *   - 代码实现简洁。
 * 缺点：
 *   - 算法理解起来有一定难度；
 *   - 需要额外的空间存储图结构。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (n == 0) return {};
 * 2. 使用更明确的变量名（如 degree 代替 d）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释为什么最终会剩下1个或2个节点。
 * 
 * 九、一句话总结
 * 通过拓扑排序逐层删除叶子节点，你的实现高效地找到了最小高度树的根节点，
 * 展现了图论算法在解决树结构问题中的应用能力。
 */